/**
*	@file StallOptimizer.cpp
*
*	@brief change the structure of AST to optimize stall
*
*	@author li yuchen
*
*	@date 1/28/2011
*/

#include "StallOptimizer.h"
#include "PKB.h"

using namespace std;

struct StallState{
	// at this stage, how many stalls
	int stalls;
	// the statement at this stage;
	vector<TNode*> stmts;
	// the remaining statments
	vector<TNode*> remain_stmts; 
};

static int optimize_step;
static TNode* DuplicateTNode(TNode* old_tnode);
static void OptimizeStmtListStall(TNode* old_stmtlist_tnode, TNode* new_stmtlist_tnode);
static void OptimizeProcedureStall(TNode* old_proc_tnode, TNode* new_proc_tnode);
static TNode* BuildOptimizeStruct(TNode* old_tnode);
static bool IsMovableStmts(vector<TNode*>& remain_stmts, int index);
static bool ShareSameVar(VarSet& precede_tnode, VarSet& current_tnode);
static int GetStallBetweenStmts(TNode* stmt_a, TNode* stmt_b);

int GetStallBetweenStmts(TNode* stmt_a, TNode* stmt_b){
	if(stmt_a->type != ASSIGN_TYPE) return 0;
	VarIdx modified_var = stmt_a->child->value;
	switch(stmt_b->type){
	case ASSIGN_TYPE:
		if(Uses::IsUsesS(stmt_b->stmt_num,modified_var)) return 1;
		return 0;
	case WHILE_TYPE: case IF_TYPE:
		if(stmt_b->child->value == modified_var) return 1;
		return 0;
	case CALL_TYPE:
		return 0;
	}
	return -9999;
}

bool ShareSameVar(VarSet& precede_tnode, VarSet& current_tnode){
	for(int i = 0; i < precede_tnode.size(); i++){
		if(precede_tnode[i] == current_tnode[i] && precede_tnode[i] == true) return true;
	}
	return false;
}

bool IsMovableStmts(vector<TNode*>& remain_stmts, int index){
	TNode* current_tnode = remain_stmts[index];
	for(int i = 0; i < index; i++){
		TNode* precede_tnode = remain_stmts[i];
		VarSet& pre_modified = Modifies::GetModifiesS(precede_tnode->stmt_num);
		VarSet& pre_used = Uses::GetUsesS(precede_tnode->stmt_num);
		VarSet& current_modified = Modifies::GetModifiesS(current_tnode->stmt_num);
		VarSet& current_used = Uses::GetUsesS(current_tnode->stmt_num);
		if(ShareSameVar(current_modified,pre_modified)) return false;
		if(ShareSameVar(current_modified,pre_used)) return false;
		if(ShareSameVar(current_used,pre_modified)) return false;
	}
	return true;
}

TNode* DuplicateExpr(TNode* old_root){
	TNode* new_root = AST::CreateTNode(old_root->type,old_root->value,old_root->stmt_num);
	if(old_root->child == NULL) return new_root;
	TNode* left_expr = DuplicateExpr(old_root->child);
	TNode* right_expr = DuplicateExpr(old_root->child->right_sibling);
	AST::SetParent(new_root,left_expr);
	AST::SetSibling(left_expr,right_expr);
	return new_root;
}

TNode* DuplicateTNode(TNode* old_tnode){
	if(old_tnode->type == ASSIGN_TYPE){
		return DuplicateExpr(old_tnode);
	}
	return AST::CreateTNode(old_tnode->type,old_tnode->value,old_tnode->stmt_num);
}

TNode* BuildOptimizeStruct(TNode* old_tnode){
	TNode* new_tnode = NULL;
	TNode* new_var_tnode = NULL;
	TNode* stmt_list1 = NULL;
	TNode* stmt_list2 = NULL;

	switch(old_tnode->type){
	case ASSIGN_TYPE:
	case CALL_TYPE:
		new_tnode = DuplicateTNode(old_tnode);
		break;
	case WHILE_TYPE:
		new_tnode = DuplicateTNode(old_tnode);
		new_var_tnode = DuplicateTNode(old_tnode->child);
		AST::SetParent(new_tnode,new_var_tnode);
		stmt_list1 = DuplicateTNode(old_tnode->child->right_sibling);
		AST::SetSibling(new_var_tnode,stmt_list1);
		OptimizeStmtListStall(old_tnode->child->right_sibling,stmt_list1);
		break;
	case IF_TYPE:
		new_tnode = DuplicateTNode(old_tnode);
		new_var_tnode = DuplicateTNode(old_tnode->child);
		AST::SetParent(new_tnode,new_var_tnode);
		stmt_list1 = DuplicateTNode(old_tnode->child->right_sibling);
		AST::SetSibling(new_var_tnode,stmt_list1);
		stmt_list2 = DuplicateTNode(old_tnode->child->right_sibling->right_sibling);
		AST::SetSibling(stmt_list1,stmt_list2);
		OptimizeStmtListStall(old_tnode->child->right_sibling,stmt_list1);
		OptimizeStmtListStall(old_tnode->child->right_sibling->right_sibling,stmt_list2);
		break;
	}
	return new_tnode;
}

void OptimizeStmtListStall(TNode* old_stmtlist_tnode, TNode* new_stmtlist_tnode){

	// build the TNode for the statements in the same AST level
	vector<TNode*> new_stmts;
	TNode* old_traverser = old_stmtlist_tnode->child;
	while(old_traverser != NULL){
		new_stmts.push_back(BuildOptimizeStruct(old_traverser));
		old_traverser = old_traverser->right_sibling;
	}

	if(new_stmts.size() == 1){
		AST::SetParent(new_stmtlist_tnode,new_stmts[0]);
		return;
	}

	stack<StallState*> stall_stack;
	int min_stall = 0;
	vector<TNode*> min_stmt_path;
	for(int i = 0; i < new_stmts.size(); i++){
		vector<TNode*> remain_path = new_stmts;
		if(IsMovableStmts(new_stmts,i)){
			TNode* moved_statement = new_stmts[i];
			remain_path.erase(remain_path.begin()+i);
			StallState* new_state = new StallState;
			new_state->stalls = 0;
			new_state->remain_stmts = remain_path;
			new_state->stmts.push_back(moved_statement);
			stall_stack.push(new_state);
		}
	}

	while(!stall_stack.empty()){
		StallState* current_state = stall_stack.top();
		stall_stack.pop();
		if(current_state->remain_stmts.size() == 1){
			current_state->stalls += GetStallBetweenStmts(
				current_state->stmts[current_state->stmts.size()-1],
				current_state->remain_stmts[0]);
			current_state->stmts.push_back(current_state->remain_stmts[0]);
			current_state->remain_stmts.clear();
			if(current_state->stalls <= min_stall){
				min_stall = current_state->stalls;
				min_stmt_path.clear();
				min_stmt_path = current_state->stmts;
			}
		}
		else{
			TNode* current_tnode = current_state->stmts[current_state->stmts.size()-1];
			int optimize_count = 0;
			int optimize_limit = (optimize_step == 0) ? current_state->remain_stmts.size() : optimize_step;
			for(int i = 0; i < min(current_state->remain_stmts.size(),optimize_limit); i++){
				vector<TNode*> remain_path = current_state->remain_stmts;
				if(IsMovableStmts(remain_path,i)){
					TNode* moved_statement = remain_path[i];
					remain_path.erase(remain_path.begin()+i);
					StallState* new_state = new StallState;
					new_state->stalls = current_state->stalls + GetStallBetweenStmts(current_tnode,moved_statement);
					new_state->remain_stmts = remain_path;
					new_state->stmts = current_state->stmts;
					new_state->stmts.push_back(moved_statement);
					stall_stack.push(new_state);
				}
			}
		}
		// delete the current_state
		current_state->remain_stmts.clear();
		current_state->stmts.clear();
		delete current_state;
	}
	
	// examine change
	int changed_stall = 0;
	int old_stall = 0;
	for(int i = 1; i < min_stmt_path.size(); i++){
		changed_stall += GetStallBetweenStmts(min_stmt_path[i-1],min_stmt_path[i]);
		old_stall += GetStallBetweenStmts(new_stmts[i-1],new_stmts[i]);
	}

	if(changed_stall == old_stall){
		min_stmt_path.clear();
		min_stmt_path = new_stmts;
	}

	// link result
	AST::SetParent(new_stmtlist_tnode,min_stmt_path[0]);
	for(int i = 1; i < min_stmt_path.size(); i++){
		AST::SetSibling(min_stmt_path[i-1],min_stmt_path[i]);
	}
}

void OptimizeProcedureStall(TNode* old_proc_tnode, TNode* new_proc_tnode){
	TNode* new_stmtlist_tnode = AST::CreateTNode(STMT_LIST_TYPE,old_proc_tnode->child->type,old_proc_tnode->child->stmt_num);
	AST::SetParent(new_proc_tnode,new_stmtlist_tnode);
	OptimizeStmtListStall(old_proc_tnode->child,new_stmtlist_tnode);
}

TNode* SimpleStallOptimize(TNode* AST_original_root, int level_optimize){
	if(level_optimize < 0){
		cout << "cannot optimize to negative search in stall optimization" << endl;
		exit(1);
	}
	optimize_step = level_optimize;

	TNode* new_AST_root_tnode = AST::CreateTNode(ROOT,NOT_APPLICABLE,NOT_APPLICABLE);
	
	TNode* traverser = AST_original_root;
	TNode* new_traverser = new_AST_root_tnode;
	
	TNode* new_proc = AST::CreateTNode(PROC_TYPE,traverser->child->value,NOT_APPLICABLE);
	AST::SetParent(new_traverser,new_proc);
	new_traverser = new_traverser->child;
	traverser = traverser->child;
	OptimizeProcedureStall(traverser,new_traverser);
	traverser = traverser->right_sibling;

	while(traverser != NULL){
		new_proc = AST::CreateTNode(PROC_TYPE,traverser->value,NOT_APPLICABLE);
		AST::SetSibling(new_traverser,new_proc);
		new_traverser = new_traverser->right_sibling;
		OptimizeProcedureStall(traverser,new_traverser);
		traverser = traverser->right_sibling;
	}
	return new_AST_root_tnode;
}